#include "pch.h"
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Trie {
private:
	bool is_string;
	Trie *next[26];
public:
	/** Initialize your data structure here. */
	Trie() {
		is_string = false;
		for (int i = 0;i < 26;i++) next[i] = nullptr;
	}

	/** Inserts a word into the trie. */
	void insert(string word) {
		Trie* node = this;
		for (char ch : word)
		{
			if (node->next[ch - 'a'] == nullptr)
			{
				node->next[ch - 'a'] = new Trie();
			}
			node = node->next[ch - 'a'];
		}
		node->is_string = true;
	}

	/** Returns if the word is in the trie. */
	bool search(string word) {
		Trie* node = this;
		for (char ch : word)
		{
			node = node->next[ch - 'a'];
			if (node == nullptr) return false;
		}
		return node->is_string;
	}

	/** Returns if there is any word in the trie that starts with the given prefix. */
	bool startsWith(string prefix) {
		Trie* node = this;
		for (char ch : prefix)
		{
			node = node->next[ch - 'a'];
			if (node == nullptr)
				return false;
		}
		return true;
	}
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

int main()
{

	return 0;
}